package com.easy.leetcode.stack;

import java.util.Stack;

/**
 * @ClassName LongestValidParentheses32
 * @Description 最长有效括号
 * @Author zheng
 * @Date 2021/11/9 15:03
 * @Version 1.0
 **/
public class LongestValidParentheses32 {

    public static int longestValidParentheses(String s) {
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if ('(' == c) {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }


    public static int longestValidParentheses1(String s) {
        int maxLength = 0;
        //以索引i位置上字符结尾的最长可匹配字符串长度
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            char c = s.charAt(i);
            //以“）”结尾
            if (c == ')') {
                //前一个字符是“(” ,那么dp[i] 为dp[i-2]+2   （如果dp[i-2]存在）;
                if (s.charAt(i - 1) == '(') {
                    dp[i] = i >= 2 ? dp[i - 2] + 2 : 2;
                } else {
                    //此处，dp[i-1]最大值为i,需要判断下
                    if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                        //dp[i] = dp[i - dp[i - 1] - 1] +;
                        //此处可能会越界
                        if (i - dp[i - 1] - 2 >= 0) {
                            dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2;
                        } else {
                            dp[i] = dp[i - 1] + 2;
                        }
                    }
                }
            }
            maxLength = Math.max(dp[i], maxLength);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        String str = "()(())";
        System.out.println(longestValidParentheses1(str));
    }
}
